We are looking at worlds that are uncertain and involve time.

Every world or environment involves time. We're interested here in environments where the changes in the world are approximately at the same time scale as our deliberation times.

So that it actually matters what we do, that time matters, so that we actually have to model it explicitly.

Remember, the basic idea is very simple. We have a couple of random variables we're interested in, and we'll just index those by a time structure.

Very simple. The first thing you would have come up with. The only thing that is slightly more interesting here is that you can take arbitrary time structures, but we're not doing that.

So we keep to the simple stuff. So we have these time structures and these random variables that are indexed by time, which gives us all kinds of infinitudes or biggitudes,

where we can have an unbounded number of dependencies or so, because all of it is potentially infinite.

So the first thing we do is we define all of that away by various assumptions. We assume that our problems are stationary, which means we always have the same transition model independent of time.

And we assume Markov properties, which essentially bounds the number of incoming influences at each node, influences from the past.

And to be really on the safe side, we actually bound that number to be 1.

There's a theory out there for 2 and 3 and n in general, but it's a little bit more difficult, so we're not doing it here.

Under these assumptions, which are surprisingly realistic. So normally all the assumptions we've done so far have been just ludicrous.

It's clear that there are almost no worlds where they really actually apply. These are actually the Markov assumptions, cover a pretty broad case of interesting examples.

And we are looking at, and that's what we did yesterday, we looked at a couple of inference procedures. Filtering or monitoring, which is updating our belief state, namely what are the possible worlds and how likely are they,

in light of a sequence of evidences. We have prediction, which is the same thing, creating or computing a belief space for future events, not just for the current unseen event.

And we looked at smoothing, which does the same thing for the past. And finally, we looked at most likely explanation and looked at the Vita-Abi algorithm that actually gave us something there.

So just to remind you, what we're doing is essentially we're using our probabilistic machinery here, plus lots of conditional independence assumptions, which are the Markov assumptions, to get a recursive algorithm for estimating state.

For estimating the posterior probability distribution of the random variables we're interested in.

And the basic idea and simplification is that from this computation we have this forward message from one to T, which we pass on recursively, and that gives us an algorithm that's constant time and constant space for every update,

which is exactly what we want for our agent. And of course, the thing you want to realise is that whenever there's a bold phase P here, and something like sums and multiplications and so on, we have huge multi-dimensional systems of equations,

which is something we're going to look at in these Markov chains.

But the upshot is we have a simple recursive or iterative algorithm that helps us a lot. And we've looked at the umbrellas example and we basically always had two movements here.

We had the kind of upward sawtooth movement, which is using the model properties, the transition model properties, to get from the old estimation and update it via what the transition model says, plus another action that basically says,

and now we have evidence, our sensor has told us something, and we take the sensor model to update again. And then you have, and you can basically forward filter through the evidence.

Prediction is essentially the same, except that we don't have the evidence here, which leads to essentially the same algorithm. But since our evidence kind of peters out in the past, we are reaching stationary points where we've essentially destroyed all the information we have by the observations.

So making predictions into the future is possible, but making long, long, long, long term prediction still possible, but we're actually not using any information there.

We're basically predicting the kind of fixed points of the system, which is fine, and there's nothing we can do about it, but that's something to keep in mind.

The next algorithm we looked at, the next fundamentally different algorithm we looked at, was the smoothing algorithm, where we have two phases. Essentially, we start at the beginning and we filter until some kind, some time, xk, for which we want to have a smooth estimation, a better estimation, given the information that comes after k.

What we do is essentially we filter all the way to now, now being the last time we have information, and then kind of play the transition model backwards to use the information we have in this latter part.

It's not very surprising that we get a recursive algorithm again, but what we're getting here is kind of a backwards message, which we again can extract from this huge system of equations.

If you look at this, you can see the smoothing part of the algorithm on top, and then you go backwards across the transition model and get better values here.

In other words, in this example, knowing that there was a second umbrella actually tells us something about rain on the first day. Why? Because we've built in the 70% staying tendency into our model.

That actually says if there's rain on day two, which we've estimated to be 90% or 88%, then that tells us something about day one, which we can kind of back propagate into this here.

That's how the algorithm works.

There is a straightforward implementation of that, which is an iterative way of doing it, which is what you would all do if given enough time and the task to implement this idea.

The final thing we looked at was most likely explanation, where you can think of as having a signal, here the umbrella signal, first two days umbrella, third day, no umbrella, then two times umbrella again, which really comes from a source, which is unknown.

What you want to know is really the source signal, rather than the transmitted signal.

You have a noisy channel.

You're interested in the most likely source signal that explains the perceived signal.

The most important thing here is that we realize that this is not absolutely trivial.

We can't do this by filtering alone.

By filtering, or possibly smoothing everything, filtering and smoothing again, that would actually give us kind of the sequence of most likely states, which may not be the most likely sequence.

Once you realize this, you realize that actually the objects we're talking about is really the sequences.

We have to lift this all, and the optimization in particular, to the sequence level, which in the end leads to an algorithm that's again tail-recursive, but has a different message, in this case this M message,

which is really about the maximizing folded into this.

That actually is called the Viterbi algorithm.

For the Viterbi algorithm, we get linear space complexity.

It isn't surprising, because we have to keep the paths in memory.

Because it's a path level algorithm, we somehow have to store the paths, or at least best candidates or something like this.

That leads the longer our paths get. Of course, we need linearly much space here.